const kUP = 0
const kDOWN = 1
const kLEFT = 2
const kRIGHT = 3
const vecIndex = [kUP, kDOWN, kLEFT, kRIGHT]
const directionVectors = [[-1, 0], [1, 0], [0, -1], [0, 1]]
const inf = maxint
const ninf = -maxint - 1
const timeLimit = 140
const emptyCellPattern =&
[[1,0,0,0],
 [1,1,0,0],
 [0,1,1,0],
 [0,0,1,1]]
const monotonicityPattern =&
 [[4,  2, 1, 0],
  [8,  4, 2, 1],
  [16, 8, 4, 2],
  [32,16, 8, 4]]
const colorMap = {
  0 	: 0,
  2  : 1,
  4  : 2,
  8  : 3,
  16 : 4,
  32 : 5,
  64 : 6,
  128 : 7,
  256 : 8,
  512 : 9,
  1024 : 10,
  2048 : 11,
  4096 : 12,
  8192 : 13,
  16384 : 14,
  32768 : 15
}
const actionDict = {
 0: "UP",
 1: "DOWN",
 2: "LEFT",
 3: "RIGHT"
}
const sz = min(xmax,ymax)/6
const offs = 15
const gap = 2
const w = window()
const bgc = rgb(15,40,15)

func Display()
  sub println(s)
    color 15, bgc
    at offs, self.y_out
    print s + chr(27) + "[K"
  end

  sub display(grid)
    local i,j,x,y,v,c

    y = 0
    x = 0
    for i = 0 to grid.size
      for j = 0 to grid.size
        v = grid.map[i][j]
        c = colorMap[v]
        color rgb(45,100,40), c
        rect x+offs, y+offs, x+offs+sz-gap, y+offs+sz-gap, c filled
        at x+offs+((sz-txtw(v))/2), y+offs+((sz-txth(v))/2)
        print v
        x += sz
      next j
      y += sz
      x = 0
    next i
    self.y_out = y + 10
    showpage
  end

  w.setFont(sz/4,0,1,0)
  color 0, bgc: cls

  local result = {}
  result.show=@display
  result.println=@println
  return result
end

func GridClass()
  func createGrid()
    local result = {}
    result.clone=@clone
    result.getAvailableCells = @getavailablecells
    result.getMaxTile = @getmaxtile
    result.canInsert = @caninsert
    result.canMove = @canmove
    result.move = @move
    result.merge = @merge
    result.getCellValue = @getCellValue
    result.setCellValue = @setCellValue
    return result
  end

  # Make a Deep Copy of This Object
  func clone()
    local result = self
    result.map = self.map
    return result
  end

  sub setCellValue(byref cell, v)
    local x,y
    (y,x) = cell
    if (v == 0) then throw "Set empty value"
    if (self.map[y][x] != 0) then throw "Overwrite non empty cell"
    self.map[y][x] = v
  end

  func getAvailableCells()
    local x,y
    dim cells
    for y = 0 to self.size
      for x = 0 to self.size
        if self.map[y][x] == 0 then
          append cells, [y,x]
        endif
      next x
    next y
    return cells
  end

  # Return the Tile with Maximum Value
  func getMaxTile()
    local x,y
    local maxTile = 0
    for y = 0 to self.size
      for x = 0 to self.size
        maxTile = max(maxTile, self.map[y][x])
      next x
    next y
    return maxTile
  end

  # Check If Able to Insert a Tile in Position
  func canInsert(byref cell)
    local x,y
    (y,x)=cell
    return getCellValue(x, y) == 0
  end

  # Move the Grid
  # 0 = "Up", 1 = "Down", 2 = "Left", 3 = "Right".
  func move(dir)
    local result
    select case dir
      case kUP: result = moveUD(True)
      case kDOWN: result = moveUD(False)
      case kLEFT: result = moveLR(True)
      case kRIGHT: result = moveLR(False)
      case else: throw "Invalid move:" + dir
    end select
    return result
  end

  # Move Up or Down
  func moveUD(move_up)
    local x,y,y1,y2,incr,moved,cells,cell,value
    dim cells(self.size)

    incr = iff(move_up, 1, -1)
    y1 = iff(move_up, 0, self.size)
    y2 = iff(move_up, self.size, 0)
    moved = False

    for x = 0 to self.size
      erase cells
      for y = y1 to y2 step incr
        cell = self.map[y][x]
        if cell != 0 then append cells, cell
      next y

      merge(cells)

      for y = y1 to y2 step incr
        if len(cells) then
          value = cells[0]
          delete cells, 0
        else
          value = 0
        endif
        if self.map[y][x] != value then
          self.map[y][x] = value
          moved = True
        endif
      next y
    next x
    return moved
  end

  # move left or right
  func moveLR(move_left)
    local x,y,x1,x2,incr,moved,cells,cell,value
    dim cells(self.size)

    incr = iff(move_left, 1, -1)
    x1 = iff(move_left, 0, self.size)
    x2 = iff(move_left, self.size, 0)
    moved = False

    for y = 0 to self.size
      erase cells
      for x = x1 to x2 step incr
        cell = self.map[y][x]
        if cell != 0 then append cells, cell
      next y
      merge(cells)
      for x = x1 to x2 step incr
        if len(cells) then
          value = cells[0]
          delete cells, 0
        else
          value = 0
        endif
        if self.map[y][x] != value then
          moved = True
          self.map[y][x] = value
        endif
      next y
    next y
    return moved
  end

  # Merge Tiles
  sub merge(byref cells)
    local num_cells = len(cells)
    if num_cells <= 1 then return
    local i = 0
    while i < len(cells) - 1
      if cells[i] == cells[i+1] then
        cells[i] *= 2
        delete cells, i+1
      endif
      i += 1
    wend
  end

  func canMove(dirs)
    local i, x, y, xm, ym, checkingMoves, adjCellValue

    # Init Moves to be Checked
    checkingMoves = IFF(len(dirs)==0, vecIndex, dirs)
    for y = 0 to self.size
      for x = 0 to self.size
        # If Current Cell is Filled
        if self.map[y][x] != 0 then
          # Look Ajacent Cell Value
          for i in checkingMoves then
            [ym, xm] = directionVectors[i]
            adjCellValue = getCellValue(x + xm, y + ym)
            # If Value is the Same or Adjacent Cell is Empty
            if adjCellValue == self.map[y][x] or adjCellValue == 0 then
              return True
            endif
          next i
        elif self.map[y][x] == 0 then
          # Current Cell is Empty
          return True
        endif
      next x
    next y
    return False
  end

  func crossBound(x, y)
    return (x < 0 or x > self.size or y < 0 or y > self.size)
  end

  func getCellValue(x, y)
    if not crossBound(x, y) then
      return self.map[y][x]
    else
      return Nil
    endif
  end

  local result = createGrid()
  result.map = [[0,0,0,0],[0,0,0,0],[0,0,0,0],[0,0,0,0]]
  result.size = 3
  return result
end

func PlayerAI()
  # https://en.wikipedia.org/wiki/Evaluation_function
  func getUtility(state)
    local x,y
    local numEmpty = 0
    local result = 0.0
    local highest = 0
    local size=state.size

    for y = 0 to size
      for x = 0 to size
        if (state.map[y][x] != 0) then
          result += state.map[y][x] * monotonicityPattern[y][x]
          if state.map[y][x] > highest then
            highest = state.map[y][x]
          endif
        else
          numEmpty += 1
        endif
      next x
    next y

    if (state.map[0][3] != highest) then
      result += highest * 100
    endif
    if (numEmpty == 0) then
      result = 0
    elif (result != 0) then
      result = 1 / result
    endif
    return result
  end

  # whether to stop evaluating lower depths
  func isTerminal(move, depth)
    if move == Nil then
      return True
    endif
    if depth >= self.maxDepth then
      return True
    endif
    if ((ticks - self.startTime) > self.timeLimit) then
      self.timeout = True
      return True
    endif
    return False
  end

  func maximise(byref state, a, b, move, depth)
    local availableMoves, child, maxMove, maxUtility, nextMove

    if (isTerminal(move, depth)) then
       return [move, getUtility(state)]
    endif

    availableMoves = False
    [maxMove, maxUtility] = [Nil, ninf]
    for nextMove in [0,3,1,2]
      child = state.clone()
      if child.move(nextMove) then
        availableMoves = True
        # get the estimated attack/response move
        [_, utility] = minimise(child, a, b, nextMove, depth + 1)
        if (utility > maxUtility) then
          [maxMove, maxUtility] = [nextMove, utility]
        endif
        if (maxUtility >= b) then
          # this node will not be selected in ancestor min function
          # we are larger than a sibling node so will be discounted
          exit for
        endif
        if (maxUtility > a) then
           a = maxUtility
        endif
      endif
    next nextmove
    if (availableMoves == False) then
      # terminal state detected
      return [move, getUtility(state)]
    endif
    return [maxMove, maxUtility]
  end

  func minimise(byref state, a, b, move, depth)
    local child,x,y,minMove,utility,emptyPos,nextMove,minUtility
    local availableCells = state.getAvailableCells()

    if (isTerminal(move, depth) or len(availableCells) == 0) then
      return [move, getUtility(state)]
    endif

    local minimisingMoves = []
    if len(availableCells) > 2 then
      # filter to cells in the top right area
      for emptyPos in availableCells:
        [y,x] = emptyPos
        if (emptyCellPattern[y][x] == 0) then
          append minimisingMoves, emptyPos
        endif
      next emptyPos
    else
      # try the remaining 1 or 2 cells
      minimisingMoves = availableCells
    endif
    if len(minimisingMoves) == 0 then
       return [move, getUtility(state)]
    endif

    [minMove, minUtility] = [Nil, inf]

    for nextMove in minimisingMoves
      child = state.clone()
      child.setcellvalue(nextMove, 2)
      [_, utility] = maximise(child, a, b, move, depth + 1)
      if (utility < minUtility) then
         [minMove, minUtility] = [move, utility]
      endif
      if (minUtility <= a) then
        exit for
      endif
      if (minUtility < b) then
        b = minUtility
      endif
    next nextmove
    return [minMove, minUtility]
  end

  func getMove(byref grid)
    local move, utility
    self.startTime = ticks
    self.timeout = False

    [move, utility] = maximise(grid, ninf, inf, 0, 0)
    if (self.tuned == False) then
      if self.timeout == True then
        self.tuned = True
      else
        self.maxDepth += 1
      endif
    endif
    return move
  end

  local result = {}
  result.getMove=@getMove
  result.getUtility=@getUtility
  result.startTime = 0
  result.startMaxScore = 0
  result.timeLimit = 105
  result.maxDepth = 4
  result.timeout = False
  result.tuned = False
  return result
end

func ComputerAI()
  func getMove(grid)
    local cells = grid.getAvailableCells()
    if len(cells) = 0 then
      return -1
    endif
    return cells[rnd * len(cells)]
  end

  local result = {}
  result.getMove=@getMove
  return result
end

func Game()
  sub updateAlarm(currTime)
    if currTime - self.prevTime > timeLimit then
      self.over = True
    else
      self.prevTime = ticks
    endif
  end

  func isGameOver()
    return not self.grid.canMove([])
  end

  func getNewTileValue()
    if rnd < self.probability then
      return self.possibleNewTiles[0]
    else
      return self.possibleNewTiles[1]
    endif
  end

  sub insertRandomTile()
    local tileValue = getNewTileValue()
    local cells = self.grid.getAvailableCells()
    local cell = cells[rnd * len(cells)]
    self.grid.setCellValue(cell, tileValue)
  end

  sub start()
    local i, playerTurn, maxTile, prevMaxTile, gridCopy, move
    local computerAI, playerAI, displayer, moveStr

    computerAI = ComputerAI()
    playerAI   = PlayerAI()
    displayer = Display()

    for i = 1 to self.initTiles
      insertRandomTile()
    next i

    displayer.show(self.grid)

    # Player AI Goes First
    playerTurn = true
    maxTile = 0

    self.prevTime = ticks

    while not isGameOver() and not self.over
      # Copy to Ensure AI Cannot Change the Real Grid to Cheat
      gridCopy = self.grid.clone()
      move = Nil
      if playerTurn then
        move = playerAI.getMove(gridCopy)
        moveStr = actionDict[move]
        displayer.println("AI move = " + moveStr)
        # Validate and set Move
        if move != Nil and move >= 0 and move < 4 then
          if self.grid.canMove([move]) then
            unused = self.grid.move(move)
            # Update maxTile
            maxTile = self.grid.getMaxTile()
            if maxTile < prevMaxTile then
              throw "maxTile now less"
            endif
            prevMaxTile = maxTile
          else
            displayer.println("Invalid PlayerAI Move")
            self.over = True
          endif
        else
          displayer.println("Invalid PlayerAI Move")
          self.over = True
        endif
      else
        move = computerAI.getMove(gridCopy)

        # Validate Move
        if isarray(move) and self.grid.canInsert(move) then
          local value = getNewtilevalue()
          self.grid.setCellValue(move, value)
          displayer.println("Played " + value + " at " + str(move))
        else
          logprint "Invalid Computer AI Move"
          self.over = True
        endif
      endif
      if not self.over then
        displayer.show(self.grid)
      endif
      # Exceeding the Time Allotted for Any Turn Terminates the Game
      updateAlarm(ticks)
      playerTurn = IFF(playerTurn, false, true)
    wend
    displayer.println("Game over. (max tile: " + self.grid.getMaxTile() + ")")
    displayer.show(self.grid)
  end

  randomize timer
  local result = {}
  result.start = @start
  result.grid = GridClass()
  result.possibleNewTiles = [2, 4]
  result.probability = 0.8
  result.initTiles = 2
  result.over = False
  return result
end

g = Game()
g.start()
pause